import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/4 9:26
 * @description 树状数组，在一段数组中，多次修改某个值，然后求区间的和
 * 对于「区间求值」问题 :
 * 1. 数组不变，求区间和：「前缀和」、「树状数组」、「线段树」
 * 2. 多次修改某个数（单点），求区间和：「树状数组」、「线段树」
 * 3. 多次修改某个区间，输出最终结果：「差分」
 * 4. 多次修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间范围大小）
 * 5. 多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间范围大小）
 */
public class BinaryIndexedTree {
    int[] tree;
    int[] nums;
    public BinaryIndexedTree(int[] nums) {
        this.tree = new int[nums.length + 1];
        this.nums = nums;
        // 注意初始化时，树状数组下标从1开始
        for (int i = 0; i < nums.length; i++) {
            add(i + 1, nums[i]);
        }
    }

    /**
     * 返回x的二进制中最低位1的数值
     * @param x x
     * @return x & -x
     */
    int lowBit(int x) {
        return x & -x;
    }

    /**
     * 查询前index个元素的前缀和
     * @param x x
     * @return 前 index的前缀和
     */
    private int query(int x) {
        int sum = 0;
        while (x > 0) {
            sum += tree[x];
            x -= lowBit(x);
        }
        return sum;
    }

    /**
     * 单点修改，把序列第index个数增加val
     * @param index index
     * @param val val
     */
    private void add(int index, int val) {
        while (index < tree.length) {
            tree[index] += val;
            index += lowBit(index);
        }
    }
}
